package pers.zc.activiti.service.impl;

import pers.zc.activiti.entity.Line;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

/**
 * @Annotion: 有向无环图
 * @ClassName: DagHuan
 * @Author: Lin Fuyuan
 * @Date: 2019/9/26  16:20
 * @Version: 1.0
 */
public class DagHuan {


    /**
     *
     */
    public static void main(String[] args) {

        List<Line> list = new ArrayList<>();
        Line line = new Line("A", "B");
        Line line1 = new Line("A", "C");
        Line line2 = new Line("D",  "G") ;
        Line line3 = new Line("B", "E");
        Line line4 = new Line("E", "H");
        Line line5 = new Line("E", "I");
        Line line6 = new Line("I", "M");
        Line line7 = new Line("C", "K");
        Line line8 = new Line("C", "F");
        Line line9 = new Line("F", "L");
        Line line10 = new Line("F", "S");
        Line line11 = new Line("C", "X");
        list.add(line);
        list.add(line1);
        list.add(line2);
        list.add(line3);
        list.add(line4);
        list.add(line5);
        list.add(line6);
        list.add(line7);
        list.add(line8);
        list.add(line9);
        list.add(line10);
        list.add(line11);
        /*初始化数据*/
        DagHuan.initArray(list, "A");
        start();
        System.out.println(numList.size());
        System.out.println(numList);
    }

    /*存所有节点状态*/
    public static boolean[] statu = null;
    /*所有节点内容*/
    public static String[] data = null;
    /*数据*/
    static List<Line> lineList = new ArrayList<>();
    /*记录每一步的数据*/
    static List<List<String>> numList = new ArrayList<>();
    /*当前步骤状态*/
    static List<String> nowList = new ArrayList<>();
    // todo 通过下标修改状态

    /*开始*/
    public static void start() {
        /*获取开始节点的所有子节点*/
        Set<String> childList = getChilds(nowList.get(0), true);
        /*遍历起始节点的子节点*/
        if (childList.size() > 0) {
            for (String node : childList) {
                boolean run = run(node);
            }
        }
    }


    /*处理当前节点 返回false 说明存在闭环 */
    public static boolean run(String node) {
        /*判断当前list是否存在 当前node  qie list.size()>0*/
        if (nowList.size() > 0 && nowList.contains(node)) {
            /*闭环*/
            return false;
        }
        String parentNode = nowList.get(nowList.size() - 1);/*获取父节点用于接下来的步骤*/
        nowList.add(node);/*添加当前节点到nowList中表示已经到了本节点*/
        statu[getIndex(node)] = true;/*修改当前节点状态为true*/
        /*如果到此没有任何子节点 则记录一条路线*/
        if (getChilds(node, true).size() == 0) {
            numList.add(new ArrayList<>(nowList));/*记录一条路线*/
            nowList.remove(nowList.size() - 1);/*当前list中清除当前node节点*/
            if(parentNode.equals(nowList.get(0))){
                return true;
            }
            nowList.remove(nowList.size() - 1);/*当前list中清除当前node节点*/
            run(parentNode);/*返回上一节点*/
        }
        /*如果此节点没有状态为false的子节点*/
        else if (getChilds(node, false).size() == 0) {
            nowList.remove(nowList.size() - 1);/*当前list中清除当前node节点*/
            if(parentNode.equals(nowList.get(0))){
                return true;
            }
            nowList.remove(nowList.size() - 1);/*当前list中清除当前node节点*/
            run(parentNode);/*返回上一节点*/
        }
        /*如果还有状态为false的子节点进入子节点*/
        if (getChilds(node, false).size() > 0) {
            run(getChilds(node, false).iterator().next());/*获取子节点中的一个节点*/
        }
        return true;
    }


    /*初始化节点准备数据*/
    public static void initArray(List<Line> list, String start) {
        lineList = list;
        Set<String> set = new TreeSet<>();
        /*获取所有的节点元素*/
        set = list.stream().map(u -> u.getId()).collect(Collectors.toSet());
        set.addAll(list.stream().map(u -> u.getFid()).collect(Collectors.toSet()));
        System.out.println(set);
        data = set.toArray(new String[list.size()]);
        statu = new boolean[set.size()];
        /*设置初始节点*/
        nowList.add(start);
        /*设置初始节点为true*/
        statu[getIndex(start)] = true;/*修改当前节点状态为true*/
    }

    /*获取节点元素下标*/
    public static int getIndex(String node) {
        if (data != null) {
            for (int i = 0; i < data.length; i++) {
                if (node.equals(data[i])) {
                    return i;
                }
            }
        }
        return -1;
    }


    /*根据当前节点获取所有状态为false的子节点 如果没有 返回null
     * @param bool  true:获取无状态子节点  false:获取状态为false的子节点
     * */
    public static Set<String> getChilds(String nowNode, boolean bool) {
        Set<String> collect = lineList.stream().filter(line -> bool ? line.getFid().equals(nowNode) : line.getFid().equals(nowNode) && !statu[getIndex(line.getId())]).map(u -> u.getId()).collect(Collectors.toSet());
        return collect;
    }

    /*判断是否还有未遍历节点 有: true  无 :false*/
    public static boolean hasfalse(String nowId) {
        for (boolean bool : statu) {
            if (!bool) {
                return true;
            }
        }
        return false;
    }


}
